package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 30. 串联所有单词的子串
 * @date 2025/5/7 15:37
 */
public class E30 {

    /**
     * <h3>方法一：回溯加KMP算法，缺点：时间复杂度超纲然后不能处理重复情况</h3>
     *
     * @param s     源字符串
     * @param words 单词数组
     * @return 结果集
     */
    public List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        char[] source = s.toCharArray();
        dfs(result, source, words, new StringBuilder(), new boolean[words.length]);
        return result;
    }

    /**
     * 回溯
     *
     * @param result  结果集
     * @param source  源字符串
     * @param words   单词数组
     * @param builder 构建字符串
     * @param visited 是否访问过
     */
    private void dfs(List<Integer> result,
                     char[] source,
                     String[] words,
                     StringBuilder builder,
                     boolean[] visited) {
        if (builder.length() == words[0].length() * words.length) {
            int index = findSubIndex(source, builder.toString().toCharArray());
            if (index != -1) result.add(index);
            return;
        }
        for (int i = 0; i < words.length; i++) {
            if (visited[i]) continue;
            builder.append(words[i]);
            visited[i] = true;
            dfs(result, source, words, builder, visited);
            visited[i] = false;
            builder.setLength(builder.length() - words[i].length());
        }
    }

    /**
     * KMP算法
     *
     * @param source 源字符串
     * @param target 模式字符串
     * @return 模式字符串在源字符串中的起始位置，如果找不到，则返回-1
     */
    private int findSubIndex(char[] source, char[] target) {
        int[] prefixSuffix = commonPrefixSuffix(target);
        int i = 0, j = 0;
        while (i < source.length && j < target.length
                && target.length - j < source.length - i) {
            if (source[i] == target[j]) {
                if (j == target.length - 1) {
                    return i - j;
                }
                i++;
                j++;
            } else if (j > 0) {
                j = prefixSuffix[j - 1];
            } else {
                i++;
            }
        }
        return -1;
    }

    /**
     * 求最长公共前缀后缀
     *
     * @param target 模式字符串
     * @return 最长公共前缀后缀
     */
    private int[] commonPrefixSuffix(char[] target) {
        int[] result = new int[target.length];
        int i = 1, j = 0;
        while (i < target.length) {
            if (target[i] == target[j]) {
                result[i++] = ++j;
            } else if (j > 0) {
                j = result[i - 1];
            } else {
                i++;
            }
        }
        return result;
    }

    /**
     * <h3>方法二：滑动窗口 + 哈希表</h3>
     *
     * @param s     源字符串
     * @param words 单词数组
     * @return 结果集
     */
    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        int wordLength = words[0].length();
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.compute(word, (k, v) -> v == null ? 1 : v + 1);
        }
        for (int i = 0; i < s.length() - wordLength * words.length + 1; i++) {
            int j = i;
            HashMap<String, Integer> countMap = new HashMap<>();
            while (j <= i + wordLength * words.length - wordLength) {
                String str = s.substring(j, j + wordLength);
                if (map.containsKey(str)) {
                    int count = countMap.compute(str, (k, v) -> v == null ? 1 : v + 1);
                    if (count > map.get(str)) {
                        break;
                    }
                    j += wordLength;
                } else {
                    break;
                }
            }
            if (j == i + wordLength * words.length) {
                result.add(i);
            }
        }
        return result;
    }

    private final HashSet<String> set = new HashSet<>();

    /**
     * <h3>方法三：回溯 + 重复项合并，缺点：不能处理所有情况，重复项会永久合并为一项，不会分开</h3>
     *
     * @param s     源字符串
     * @param words 单词数组
     * @return 结果集
     */
    public List<Integer> findSubstring(String s, String[] words) {
        int wordLength = words[0].length();
        int totalLength = wordLength * words.length;
        List<Integer> result = new ArrayList<>();
        List<String> wordsDuplicate = handleWords(words);
        dfsAllString(wordsDuplicate,
                new StringBuilder(),
                new boolean[wordsDuplicate.size()],
                totalLength);
        for (int i = 0; i <= s.length() - totalLength; i++) {
            String str = s.substring(i, i + totalLength);
            if (set.contains(str)) {
                result.add(i);
            }
        }
        return result;
    }

    /**
     * 处理重复项
     *
     * @param words 单词数组
     * @return 处理后的单词数组
     */
    private List<String> handleWords(String[] words) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.compute(word, (k, v) -> v == null ? 1 : v + 1);
        }
        List<String> wordsDuplicate = new ArrayList<>();
        map.forEach(
                (k, v) -> wordsDuplicate.add(String.valueOf(k).repeat(Math.max(0, v)))
        );
        return wordsDuplicate;
    }

    /**
     * 回溯
     *
     * @param wordsDuplicate 处理后的单词数组
     * @param curr           当前字符串
     * @param visited        是否访问过
     * @param totalLength    总长度
     */
    private void dfsAllString(List<String> wordsDuplicate,
                              StringBuilder curr,
                              boolean[] visited,
                              int totalLength) {
        if (curr.length() == totalLength) {
            set.add(curr.toString());
            return;
        }
        for (int i = 0; i < wordsDuplicate.size(); i++) {
            if (visited[i]) continue;
            curr.append(wordsDuplicate.get(i));
            visited[i] = true;
            dfsAllString(wordsDuplicate, curr, visited, totalLength);
            visited[i] = false;
            curr.setLength(curr.length() - wordsDuplicate.get(i).length());
        }
    }
}
